<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
The Role of Propia and CHR in Problem Modelling
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial108.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial110.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc213">15.2</A>&nbsp;&nbsp;The Role of Propia and CHR in Problem Modelling</H2>
<A NAME="@default383"></A>
To formulate and solve a problem in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> the standard pattern is
as follows:
<OL CLASS="enumerate" type=1><LI CLASS="li-enumerate">
Initialise the problem variables
<LI CLASS="li-enumerate">State the constraints
<LI CLASS="li-enumerate">Specify the search behaviour
</OL>
Very often, however, the constraints involve logical implications or
disjunctions, as in the case of the <EM>noclash</EM> constraint above. 
Such constraints are most naturally formulated in a way that would
introduce choice points during the constraint posting phase. 
The two ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> clauses defining <EM>noclash</EM>, above, are a case in
point. <BR>
<BR>
There are two major disadvantages of introducing choice points during
constraint posting:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Posting and reposting constraints during search is an
unnecessary and computationally expensive overhead
<LI CLASS="li-itemize">Mixing constraint behaviour and search behaviour makes it harder
to explore and optimize the algorithm executed by the program.
</UL>
Propia and CHR's support the separation of constraint setup and search
behaviour, by allowing constraints to be formulated naturally without
their execution setting up any choice points.<BR>
<BR>
The effect on performance is illustrated by the following small
example.
The aim is to choose a set of 9 products (<CODE>Products</CODE>,
identified by their product number 101-109) to
manufacture, with a 
limited quantity of raw materials (<CODE>Raw1</CODE> and <CODE>Raw2</CODE>), 
so as to achieve a profit (<CODE>Profit</CODE>) of over
40. 
The amount of raw materials (of two kinds) needed to produce
each product is listed in a table, together with its profit.<BR>
<BR>
<A NAME="@default384"></A>
<A NAME="@default385"></A>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
product_plan(Products) :-
    length(Products,9),
    Raw1 #=&lt; 95,
    Raw2 #=&lt; 95,
    Profit #&gt;= 40,
    sum(Products,Raw1,Raw2,Profit),
    labeling(Products).

product( 101,1,19,1).  product( 102,2,17,2).  product( 103,3,15,3).
product( 104,4,13,4).  product( 105,10,8,5).  product( 106,16,4,4).
product( 107,17,3,3).  product( 108,18,2,2).  product( 109,19,1,1).

sum(Products,Raw1,Raw2,Profit) :-
    ( foreach(Item,Products),
      foreach(R1,R1List),
      foreach(R2,R2List),
      foreach(P,PList)
    do
        product(Item,R1,R2,P)
    ),
    Raw1 #= sum(R1List),
    Raw2 #= sum(R2List),
    Profit #= sum(PList).

</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The drawback of this program is that the <CODE>sum</CODE> constraint calls
<CODE>product</CODE> which chooses an item and leaves a choice point at each
call. 
Thus the setup of the <CODE>sum</CODE> constraint leaves 9 choice points.
Try running it, and the program
fails to terminate within a reasonable amount of time.<BR>
<BR>
Now to make the program run efficiently, we can simply annotate the call
to <CODE>product</CODE> as a Propia constraint making:
<CODE>product(Item,R1,R2,P) infers most</CODE>.
This program leaves no choice points during constraint setup, and
finds a solution in a fraction of a second.<BR>
<BR>
In the remainder of this chapter we show how to use Propia and CHR's,
give some 
examples, and outline their implementation.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
Propia and CHRs can be used to build clear problem models that have no
(hidden) choice points.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 15.2: Modelling without Choice Points</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial108.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial110.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
